package main;

import java.util.*;

/**
 * @author zhx
 * @since 2020-07-13
 * 给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。
 * <p>
 * 如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。
 * <p>
 * 请你返回排序后的数组。
 * <p>
 *  
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/sort-integers-by-the-number-of-1-bits
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode29 {
    public int[] sortByBits(int[] arr) {
        int[] result = new int[arr.length];
        SortedSet<Integer> counts = new TreeSet<>();
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i : arr) {
            int sum = Integer.bitCount(i);
            counts.add(sum);
            if (map.containsKey(sum)) {
                List<Integer> list = map.get(sum);
                list.add(i);
            } else {
                List<Integer> list = new ArrayList<>();
                list.add(i);
                map.put(sum, list);
            }
        }
        List<Integer> res = new ArrayList<>();
        for (Integer i:counts){
            List<Integer> list = map.get(i);
            Collections.sort(list);
            res.addAll(list);
        }
        int index = 0;
        for (int i : res){
            result[index] = i;
            index++;
        }

        return result;
    }

    private int countString(String s) {
        int sum = 0;
        for (char c : s.toCharArray()) {
            sum += Integer.parseInt(String.valueOf(c));
        }
        return sum;
    }


}
